GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Semidefinite Programmierung</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Semidefinite Programmierung</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>In der <b>semidefiniten Programmierung</b> (<b>SDP</b>, auch <b>semidefinite Optimierung</b>) werden <a href="Optimierung_(Mathematik)" class="mw-redirect" title="Optimierung (Mathematik)">Optimierungsprobleme</a> untersucht, deren Variablen keine Vektoren, sondern <a href="Symmetrische_Matrix" title="Symmetrische Matrix">symmetrische Matrizen</a> sind. Als Nebenbedingung wird verlangt, dass diese Matrizen positiv (oder negativ) <a href="Definitheit" title="Definitheit">semidefinit</a> sind, woraus sich der Name der Problemstellung ergibt.

</p><p>Anwendungen gibt es auf dem Gebiet der <a href="Approximationstheorie" class="mw-redirect" title="Approximationstheorie">Approximationstheorie</a>, der <a href="Kontrolltheorie" title="Kontrolltheorie">Kontrolltheorie</a>, der <a href="Kombinatorische_Optimierung" title="Kombinatorische Optimierung">kombinatorischen Optimierung</a>, der <a href="Optimal_Experimental_Design" class="mw-redirect" title="Optimal Experimental Design">optimalen Versuchsplanung</a> und in der Technik.

</p>

<div class="mw-heading mw-heading2"><h2 id="Problemformulierung">Problemformulierung</h2></div>

<p>Gegeben sei der reelle <a href="Vektorraum" title="Vektorraum">Vektorraum</a> der reellen, symmetrischen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\times n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/59d2b4cb72e304526cf5b5887147729ea259da78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.63ex; height:1.676ex;" alt="{\displaystyle n\times n}" loading="lazy"></span> Matrizen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S^{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ee006452a59bf1eb29983b4412348b66517a2d23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.74ex; height:2.343ex;" alt="{\displaystyle S^{n}}" loading="lazy"></span> versehen mit dem <a href="Frobenius-Skalarprodukt" title="Frobenius-Skalarprodukt">Frobenius-Skalarprodukt</a>

</p>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle A,B\rangle _{F}=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}b_{ij}=\operatorname {tr} (A^{T}B)=\operatorname {tr} (AB^{T})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/28c3f5757fb06fc75a3c3d69fd1b8e6a36de60cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:46.819ex; height:7.176ex;" alt="{\displaystyle \langle A,B\rangle _{F}=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}b_{ij}=\operatorname {tr} (A^{T}B)=\operatorname {tr} (AB^{T})}" loading="lazy"></span>.</dd></dl>

<p>Hierbei ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {tr} }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {tr} }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7e779faa4557258ea25e8101f307317fc771a1ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.816ex; height:2.009ex;" alt="{\displaystyle \operatorname {tr} }" loading="lazy"></span> die <a href="Spur_(Mathematik)" title="Spur (Mathematik)">Spur</a> einer Matrix.

</p><p>Des Weiteren sei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{+}^{n}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{+}^{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/240d3bf455b3a3f9e8a8cb0cc4ad531e0444d14b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.936ex; height:2.843ex;" alt="{\displaystyle S_{+}^{n}}" loading="lazy"></span> der <a href="Kegel_(Lineare_Algebra)" title="Kegel (Lineare Algebra)">Kegel</a> der <a href="Definitheit" title="Definitheit">symmetrischen, positiv semidefiniten Matrizen</a> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \preccurlyeq _{S_{+}^{n}}}">

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \preccurlyeq _{S_{+}^{n}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8dd1391bd477ed315fcba35b131c313b164bf2ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:4.25ex; height:2.843ex;" alt="{\displaystyle \preccurlyeq _{S_{+}^{n}}}" loading="lazy"></span> die durch diesen Kegel definierte <a href="Verallgemeinerte_Ungleichung" title="Verallgemeinerte Ungleichung">verallgemeinerte Ungleichung</a>, die sogenannte <a href="Loewner-Halbordnung" title="Loewner-Halbordnung">Loewner-Halbordnung</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Normalform">Normalform</h3></div>

<p>Das Optimierungsproblem

</p>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mtd>

<mtd>

<mtext>(positiv semidefinitheit)</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{F}&\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{S_{+}^{n}}0&\,{\text{(positiv semidefinitheit)}}\\&\langle {A_{i}},{X}\rangle _{F}=b_{i}&\,{\text{ für }}i=1,\dots ,m\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2dc7381a8fe32f8efa918abd8a10a139f2459ed0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.262ex; margin-bottom: -0.242ex; width:75.915ex; height:10.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{F}&\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{S_{+}^{n}}0&\,{\text{(positiv semidefinitheit)}}\\&\langle {A_{i}},{X}\rangle _{F}=b_{i}&\,{\text{ für }}i=1,\dots ,m\end{aligned}}}" loading="lazy"></span></dd></dl>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C,X,A_{i}\in S^{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/afac098e1a79c7bc25c41d2f6a4b16c28c77809c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.938ex; height:2.676ex;" alt="{\displaystyle C,X,A_{i}\in S^{n}}" loading="lazy"></span> ist ein <b>lineares semidefinites Programm</b> oder einfach <b>semidefinites Programm</b> (kurz SDP) in Normalform. Gesucht wird also eine reelle, symmetrische Matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span>, die positiv semidefinit ist, deren Skalarprodukt mit vorgegebenen Matrizen einen bestimmten Wert annimmt und die maximal bezüglich des Frobenius-Skalarprodukts ist. Manchmal werden auch die <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"></span> Gleichungsnebenbedingungen zusammengefasst durch eine Lineare Funktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(X):S^{n}\mapsto \mathbb {R} ^{m}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(X):S^{n}\mapsto \mathbb {R} ^{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8faa158f73f729ab3628823a90bbc8ea6b7f0ad6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.017ex; height:2.843ex;" alt="{\displaystyle L(X):S^{n}\mapsto \mathbb {R} ^{m}}" loading="lazy"></span>, die durch

</p>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(X):={\begin{pmatrix}\langle {A_{1}},{X}\rangle _{F}\\\vdots \\\langle {A_{m}},{X}\rangle _{F}\end{pmatrix}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8e0ccef4ebf97923e85e6bc920a79e6f263753af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.838ex; width:23.64ex; height:10.843ex;" alt="{\displaystyle L(X):={\begin{pmatrix}\langle {A_{1}},{X}\rangle _{F}\\\vdots \\\langle {A_{m}},{X}\rangle _{F}\end{pmatrix}}}" loading="lazy"></span></dd></dl>

<p>definiert ist. Dann lauten die Ungleichungsnebenbedingungen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(X)=b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(X)=b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/398757bb11812da5592cbcee96dbf8bb2dafd345.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.468ex; height:2.843ex;" alt="{\displaystyle L(X)=b}" loading="lazy"></span> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\in \mathbb {R} ^{m}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\in \mathbb {R} ^{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9fe71914e3d9fef4bce68f7b60693cc94feffde4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.191ex; height:2.343ex;" alt="{\displaystyle b\in \mathbb {R} ^{m}}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Ungleichungsform">Ungleichungsform</h3></div>

<p>Analog zu linearen Optimierungsproblemen existiert auch die Ungleichungsform eines SDPs:

</p>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&x_{1}A_{1}+\dots +x_{m}A_{m}\preccurlyeq _{S_{+}^{n}}B\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f7fa460200b3a35944d35a23e986b0744f8ef9aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:58.042ex; height:6.843ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&x_{1}A_{1}+\dots +x_{m}A_{m}\preccurlyeq _{S_{+}^{n}}B\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,c\in \mathbb {R} ^{m}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,c\in \mathbb {R} ^{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/191051a7a673c7bca7a1e3a31dab31e670036f67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.564ex; height:2.676ex;" alt="{\displaystyle x,c\in \mathbb {R} ^{m}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{i},B\in S^{n}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{i},B\in S^{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ca551dfd9a853eda2101b6e799ce3fbf7805f9ef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.921ex; height:2.676ex;" alt="{\displaystyle A_{i},B\in S^{n}}" loading="lazy"></span> sind. Gelegentlich wird die Ungleichungsform auch geschrieben als

</p>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&x_{1}A_{1}+\dots +x_{m}A_{m}+S=B\\&S\succcurlyeq _{S_{+}^{n}}0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/afb723c6dcbfa10baca1dffae375cad42bf57975.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.338ex; width:59.939ex; height:9.843ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&x_{1}A_{1}+\dots +x_{m}A_{m}+S=B\\&S\succcurlyeq _{S_{+}^{n}}0\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Hierbei entspricht <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> der Einführung einer <a href="Schlupfvariable" title="Schlupfvariable">Schlupfvariable</a>. Diese Form wird gerne gewählt, um Analogien zu den linearen Programmen klarzumachen. Auch hier wird gelegentlich eine lineare Funktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L^{*}(x):\mathbb {R} ^{m}\mapsto S^{n}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L^{*}(x):\mathbb {R} ^{m}\mapsto S^{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b38564b36ff0fe2db9411f4a146cc13aafeb99d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.421ex; height:2.843ex;" alt="{\displaystyle L^{*}(x):\mathbb {R} ^{m}\mapsto S^{n}}" loading="lazy"></span> definiert durch

</p>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L^{*}(x)=x_{1}A_{1}+\dots +x_{m}A_{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/46583ba63c6624204a19ce255b8083ac8238a734.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.883ex; height:2.843ex;" alt="{\displaystyle L^{*}(x)=x_{1}A_{1}+\dots +x_{m}A_{m}}" loading="lazy"></span>,</dd></dl>

<p>um die Notation zu vereinfachen und spätere Dualitätsaussagen klarer zu machen.

</p>

<div class="mw-heading mw-heading3"><h3 id="Ohne_verallgemeinerte_Ungleichungen">Ohne verallgemeinerte Ungleichungen</h3></div>

<p>Formuliert man SDP ohne verallgemeinerte Ungleichungen, so werden die Bedingungen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\succcurlyeq _{S_{+}^{n}}0}">

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\succcurlyeq _{S_{+}^{n}}0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f995e3c54f8ca642d2522aba9cd554b63c2f2438.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:8.683ex; height:3.009ex;" alt="{\displaystyle X\succcurlyeq _{S_{+}^{n}}0}" loading="lazy"></span> (Normalform) und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\succcurlyeq _{S_{+}^{n}}0}">

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\succcurlyeq _{S_{+}^{n}}0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6779dabefec573c7364ac0549a55f3bdb052e82d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:8.202ex; height:3.009ex;" alt="{\displaystyle S\succcurlyeq _{S_{+}^{n}}0}" loading="lazy"></span> (Ungleichungsform mit Schlupfvariable) meist ausgeschrieben als „<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> (bzw- <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span>) ist positiv semidefinit“.

</p>

<div class="mw-heading mw-heading3"><h3 id="Nichtlineare_semidefinite_Programme">Nichtlineare semidefinite Programme</h3></div>

<p>Gelegentlich werden auch nichtlineare semidefinite Programme betrachtet, diese haben dann entweder keine lineare Zielfunktion mehr oder nichtlineare Restriktionen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Klassifikation_und_Spezialfälle"><span id="Klassifikation_und_Spezialf.C3.A4lle"></span>Klassifikation und Spezialfälle</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Als_konvexe_Optimierungsprobleme">Als konvexe Optimierungsprobleme</h3></div>

<p>Semidefinite Programme sind immer <a href="Konvexe_Optimierung" title="Konvexe Optimierung">konvexe Optimierungsprobleme</a>. Dies folgt daraus, dass alle Gleichungsrestriktionen immer affin-linear sind und alle Ungleichungsrestriktionen (unter Verwendung von verallgemeinerten Ungleichungen) immer affin-linear sind und damit auch immer <a href="K-konvexe_Funktion" title="K-konvexe Funktion">K-konvexe Funktionen</a> sind. Damit ist die Restriktionsmenge konvex. Da außerdem die Zielfunktion immer linear ist, handelt es sich immer um ein (abstraktes oder verallgemeinertes) konvexes Problem, unabhängig ob es als Minimierungsproblem oder als Maximierungsproblem formuliert ist.

</p>

<div class="mw-heading mw-heading3"><h3 id="Als_konisches_Programm">Als konisches Programm</h3></div>

<p>Semidefinite Programme sind <a href="Konisches_Programm" title="Konisches Programm">konische Programme</a> auf dem Vektorraum der symmetrischen reellen Matrizen versehen mit dem Frobenius-Skalarprodukt und unter Verwendung des Kegels der positiv semidefiniten Matrizen. Der lineare Unterraum des <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S^{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ee006452a59bf1eb29983b4412348b66517a2d23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.74ex; height:2.343ex;" alt="{\displaystyle S^{n}}" loading="lazy"></span> wird in der Normalform durch den Kern der Abbildung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L:S^{n}\mapsto \mathbb {R} ^{m}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L:S^{n}\mapsto \mathbb {R} ^{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/350879a6ccf35cfba514f54798c61485895e3fc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.227ex; height:2.343ex;" alt="{\displaystyle L:S^{n}\mapsto \mathbb {R} ^{m}}" loading="lazy"></span>, also durch die <a href="L%C3%B6sungsmenge" title="Lösungsmenge">Lösungsmenge</a> der Gleichung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(X)=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(X)=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b470465fa7f50c053a590d1a095cd9cdf017a21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.633ex; height:2.843ex;" alt="{\displaystyle L(X)=0}" loading="lazy"></span>, beschreiben. In der Ungleichungsform mit Schlupfvariable wird der Unterraum durch das Bild der Abbildung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L^{*}:\mathbb {R} ^{m}\mapsto S^{n}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L^{*}:\mathbb {R} ^{m}\mapsto S^{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d63760565daa7603b86cd005b3804a261c3bfe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.282ex; height:2.343ex;" alt="{\displaystyle L^{*}:\mathbb {R} ^{m}\mapsto S^{n}}" loading="lazy"></span> beschrieben.

</p>

<div class="mw-heading mw-heading3"><h3 id="Spezialfall_lineare_Programme">Spezialfall lineare Programme</h3></div>

<p>Ein Spezialfall eines semidefiniten Programmes ist ein <a href="Lineare_Optimierung" title="Lineare Optimierung">lineares Programm</a>. Dazu ersetzt man alle auftretenden Matrizen durch Diagonalmatrizen. Dadurch reduziert sich die Anforderung, dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> positiv semidefinit sein soll, zu <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}\geq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/90a99710f61d5dea19e49ae5b31164d2b56b07e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.39ex; height:2.509ex;" alt="{\displaystyle x_{i}\geq 0}" loading="lazy"></span>, das Frobenius-Skalarprodukt geht zum <a href="Standardskalarprodukt" title="Standardskalarprodukt">Standardskalarprodukt</a> über und damit werden die Gleichungsrestriktionen zu einem linearen Gleichungssystem.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

<p>Will man eine symmetrische Matrix finden, für die die Summe der k größten <a href="Eigenwert" class="mw-redirect" title="Eigenwert">Eigenwerte</a> so klein wie möglich ist, kann man das als Problem der semidefiniten Programmierung formulieren. Dabei minimiert man als Zielfunktion die Variable t, von der man in einer Nebenbedingung fordert, dass sie größer oder gleich der Summe der k größten Eigenwerte von X ist. Diese Nebenbedingung ist sehr schwierig zu handhaben, weil es keine leicht zu berechnende Funktion gibt, die zu einer Matrix die Eigenwerte angibt, schon gar nicht in einer sortierten Form. Allerdings kann man die Nebenbedingung äquivalent durch die folgenden drei Bedingungen ausdrücken:<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t-ks-\mathrm {tr} (Z)\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/82dc41c4b16f8c9fc2445043a00e80e6a7a6daad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.389ex; height:2.843ex;" alt="{\displaystyle t-ks-\mathrm {tr} (Z)\geq 0}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z\succeq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a4d9ec2f113e2323998823e8c9f8b71a930904b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.941ex; height:2.343ex;" alt="{\displaystyle Z\succeq 0}" loading="lazy"></span></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z-X+sE\succeq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d0a8f0cbc17759a363c1824e0d629d42ac72fe0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:16.468ex; height:2.343ex;" alt="{\displaystyle Z-X+sE\succeq 0}" loading="lazy"></span>.</li></ol>

<p>Dabei ist E die <a href="Einheitsmatrix" title="Einheitsmatrix">Einheitsmatrix</a>, t und s sind reelle Variablen, X und Z sind Matrixvariablen. Diese Bedingungen sind mathematisch leichter zu behandeln, obwohl sie auf den ersten Blick schwieriger aussehen. Alle lassen sich einfach berechnen, da sie linear in den Variablen sind. Auch die Berechnung der Spur ist einfach. Für die Überprüfung auf positive Semidefinitheit für die zweite und dritte Bedingung gibt es spezielle Verfahren, die dann zur Lösung des Problems herangezogen werden.

</p>

<div class="mw-heading mw-heading2"><h2 id="Dualität"><span id="Dualit.C3.A4t"></span>Dualität</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Lagrange-Dualität"><span id="Lagrange-Dualit.C3.A4t"></span>Lagrange-Dualität</h3></div>

<p>Ist ein SDP in Normalform gegeben durch

</p>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mtd>

<mtd>

<mtext>(positive Semidefinitheit)</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{F}&\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{S_{+}^{n}}0&\,{\text{(positive Semidefinitheit)}}\\&\langle {A_{i}},{X}\rangle _{F}=b_{i}&\,{\text{für }}i=1,\dots ,m\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9b1850e56833a25c43de267599a10ae6f88091a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.262ex; margin-bottom: -0.242ex; width:77.323ex; height:10.176ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{F}&\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{S_{+}^{n}}0&\,{\text{(positive Semidefinitheit)}}\\&\langle {A_{i}},{X}\rangle _{F}=b_{i}&\,{\text{für }}i=1,\dots ,m\end{aligned}}}" loading="lazy"></span>,</dd></dl>

<p>so lässt sich das duale Problem bezüglich der <a href="Lagrange-Dualit%C3%A4t" title="Lagrange-Dualität">Lagrange-Dualität</a> wie folgt formulieren. Man formuliert die Gleichungsnebenbedingungen um zu <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -\langle {A_{i}},{X}\rangle _{F}+b_{i}=0}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -\langle {A_{i}},{X}\rangle _{F}+b_{i}=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7aade83a8c7569fb5b86fb7dd8a98616494afbcd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.536ex; height:2.843ex;" alt="{\displaystyle -\langle {A_{i}},{X}\rangle _{F}+b_{i}=0}" loading="lazy"></span>. Damit erhält man als Lagrange-Funktion

</p>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(X,\Lambda ,\mu )=\langle {C},{X}\rangle _{F}+\langle {-X},{\Lambda }\rangle _{F}+\sum _{i=1}^{m}\mu _{i}(-\langle {A_{i}},{X}\rangle _{F}+b_{i})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/84b851f6f1c7584ae76c3d2e45b342799d478112.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:60.022ex; height:6.843ex;" alt="{\displaystyle L(X,\Lambda ,\mu )=\langle {C},{X}\rangle _{F}+\langle {-X},{\Lambda }\rangle _{F}+\sum _{i=1}^{m}\mu _{i}(-\langle {A_{i}},{X}\rangle _{F}+b_{i})}" loading="lazy"></span>.</dd></dl>

<p>und unter Ausnutzung der <a href="Selbstdualer_Kegel" class="mw-redirect" title="Selbstdualer Kegel">Selbstdualität</a> des semidefiniten Kegels das duale Problem

</p>

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&\mu ^{T}b\\{\text{unter den Nebenbedingungen }}&\mu _{1}A_{1}+\dots +\mu _{m}A_{m}-\Lambda =-C\\&\Lambda \succcurlyeq _{S_{+}^{n}}0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ad37f59e4fb01ab4c0d62a389e9500b4150b9eac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.338ex; width:62.008ex; height:9.843ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&\mu ^{T}b\\{\text{unter den Nebenbedingungen }}&\mu _{1}A_{1}+\dots +\mu _{m}A_{m}-\Lambda =-C\\&\Lambda \succcurlyeq _{S_{+}^{n}}0\end{aligned}}}" loading="lazy"></span>.</dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Lambda }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ac0a4a98a414e3480335f9ba652d12571ec6733.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.613ex; height:2.176ex;" alt="{\displaystyle \Lambda }" loading="lazy"></span> fungiert hier als Schlupfvariable. Dies ist ein SDP in Ungleichungsform. Für das genaue Vorgehen siehe <a href="Konisches_Programm#Lagrange-Dualität" title="Konisches Programm">Lagrange-Dualität konischer Programme</a>.

</p><p>Analog zu den konischen Programmen erhält man auch als duales Problem eines SDPs in Ungleichungsform

</p>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&x_{1}A_{1}+\dots +x_{m}A_{m}\preccurlyeq _{S_{+}^{n}}B\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f7fa460200b3a35944d35a23e986b0744f8ef9aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:58.042ex; height:6.843ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&x_{1}A_{1}+\dots +x_{m}A_{m}\preccurlyeq _{S_{+}^{n}}B\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>das SDP in Normalform

</p>

<mtr>

<mtd>

<mtext>Maximiere </mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Maximiere }}&s(\Lambda )=-\langle {\Lambda },{B}\rangle _{F}&\\{\text{unter den Nebenbedingungen }}&\Lambda \succcurlyeq _{S_{+}^{n}}&\\&\langle {\Lambda },{A_{i}}\rangle _{F}=-c_{i}&i=1,\dots ,m\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b813340359ff4f2fad324e270ac5fd5267db6eeb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.983ex; margin-bottom: -0.189ex; width:64.759ex; height:9.509ex;" alt="{\displaystyle {\begin{aligned}{\text{Maximiere }}&s(\Lambda )=-\langle {\Lambda },{B}\rangle _{F}&\\{\text{unter den Nebenbedingungen }}&\Lambda \succcurlyeq _{S_{+}^{n}}&\\&\langle {\Lambda },{A_{i}}\rangle _{F}=-c_{i}&i=1,\dots ,m\end{aligned}}}" loading="lazy"></span>,</dd></dl>

<p>Somit sind die SDPs abgeschlossen bezüglich der Lagrange-Dualität und das duale Problem des dualen Problems ist stets wieder das primale Problem. Außerdem gilt stets die <a href="Schwache_Dualit%C3%A4t" class="mw-redirect" title="Schwache Dualität">schwache Dualität</a>, also dass der Zielfunktionswert des dualen Problems stets kleiner ist als der Zielfunktionswert des primalen Problems. Ist außerdem die <a href="Slater-Bedingung" title="Slater-Bedingung">Slater-Bedingung</a> erfüllt (siehe unten), so gilt die <a href="Starke_Dualit%C3%A4t" class="mw-redirect" title="Starke Dualität">starke Dualität</a>, die Optimalwerte des primalen und des dualen Problems stimmen also überein.

</p>

<div class="mw-heading mw-heading3"><h3 id="Dualität_konischer_Programme"><span id="Dualit.C3.A4t_konischer_Programme"></span>Dualität konischer Programme</h3></div>

<p>Fasst man SDPs als abstrakte konische Programme auf, so lässt sich der lineare Unterraum <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {L}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {L}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9027196ecb178d598958555ea01c43157d83597c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.604ex; height:2.176ex;" alt="{\displaystyle {\mathcal {L}}}" loading="lazy"></span> durch die oben beschriebene lineare Funktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L:S^{n}\mapsto \mathbb {R} ^{m}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L:S^{n}\mapsto \mathbb {R} ^{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/350879a6ccf35cfba514f54798c61485895e3fc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.227ex; height:2.343ex;" alt="{\displaystyle L:S^{n}\mapsto \mathbb {R} ^{m}}" loading="lazy"></span> beschreiben. Er ist dann genau die Lösungsmenge der Gleichung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(X)=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(X)=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b470465fa7f50c053a590d1a095cd9cdf017a21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.633ex; height:2.843ex;" alt="{\displaystyle L(X)=0}" loading="lazy"></span>. Somit lässt sich das primale konische Problem als SDP in Normalform schreiben.

</p>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{F}\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{S_{+}^{n}}0\\&L(X)-b=0\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/031bd61a5b2d7324e203080098cca65e637b583c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.983ex; margin-bottom: -0.189ex; width:46.76ex; height:9.509ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{F}\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{S_{+}^{n}}0\\&L(X)-b=0\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Hierbei sei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(B)=b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(B)=b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ecae996821e827f5af5815d751997e013ecb4f07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.252ex; height:2.843ex;" alt="{\displaystyle L(B)=b}" loading="lazy"></span>. Der für das duale Problem nötige Orthogonalraum wird dann durch den zu <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span> <a href="Adjungierter_Operator" title="Adjungierter Operator">adjungierten Operator</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L^{*}:\mathbb {R} ^{m}\mapsto S^{n}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L^{*}:\mathbb {R} ^{m}\mapsto S^{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d63760565daa7603b86cd005b3804a261c3bfe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.282ex; height:2.343ex;" alt="{\displaystyle L^{*}:\mathbb {R} ^{m}\mapsto S^{n}}" loading="lazy"></span>, der durch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L^{*}(x)=x_{1}A_{1}+\dots +x_{m}A_{m}}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L^{*}(x)=x_{1}A_{1}+\dots +x_{m}A_{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/46583ba63c6624204a19ce255b8083ac8238a734.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.883ex; height:2.843ex;" alt="{\displaystyle L^{*}(x)=x_{1}A_{1}+\dots +x_{m}A_{m}}" loading="lazy"></span> definiert ist, beschrieben. Somit lautet das konische duale Problem:

</p>

<mtr>

<mtd>

<mtext>Minimiere </mtext>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>unter den Nebenbedingungen </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(Y)=\langle {B},{Y}\rangle _{F}\\{\text{unter den Nebenbedingungen }}&Y\succcurlyeq _{S_{+}^{n}}0\\&Y=L^{*}(y)+C,\,y\in \mathbb {R} ^{m}\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/250d969700932014ad21ee770bfc4c96a101c396.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.983ex; margin-bottom: -0.189ex; width:54.58ex; height:9.509ex;" alt="{\displaystyle {\begin{aligned}{\text{Minimiere }}&s(Y)=\langle {B},{Y}\rangle _{F}\\{\text{unter den Nebenbedingungen }}&Y\succcurlyeq _{S_{+}^{n}}0\\&Y=L^{*}(y)+C,\,y\in \mathbb {R} ^{m}\end{aligned}}}" loading="lazy"></span>.</dd></dl>

<p>Das duale Problem ist dann also ein SDP in Ungleichungsform mit Schlupfvariable. Es gilt dann stets für alle zulässigen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X,Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X,Y}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8705438171d938b7f59cd1bfa5b7d99b6afa5cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.787ex; height:2.509ex;" alt="{\displaystyle X,Y}" loading="lazy"></span>

</p>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle {C},{X}\rangle _{F}+\langle {B},{Y}\rangle _{F}\geq \langle {B},{C}\rangle _{F}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4ab1fbb76e65bedc1c59d0191c5ea5e36c8d7dcf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.672ex; height:2.843ex;" alt="{\displaystyle \langle {C},{X}\rangle _{F}+\langle {B},{Y}\rangle _{F}\geq \langle {B},{C}\rangle _{F}}" loading="lazy"></span></dd></dl>

<p>Ist die Slater-Bedingung erfüllt (siehe unten) und das primale Problem hat einen endlichen Optimalwert <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/180f741aa3ec0ac9e97e4777842b446c75bd4fa0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.676ex;" alt="{\displaystyle p^{*}}" loading="lazy"></span>, so hat das duale Problem eine Optimallösung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5df6b56e280c170dd2e9844b966dd0f1aeb12ea0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:2.954ex; height:2.176ex;" alt="{\displaystyle Y^{*}}" loading="lazy"></span>, und es gilt

</p>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p^{*}+\langle {B},{Y^{*}}\rangle _{F}=\langle {B},{C}\rangle _{F}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87b389e376c466d52e494613ab0bc869508ace56.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:25.114ex; height:2.843ex;" alt="{\displaystyle p^{*}+\langle {B},{Y^{*}}\rangle _{F}=\langle {B},{C}\rangle _{F}}" loading="lazy"></span>.</dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Slater-Bedingung">Slater-Bedingung</h3></div>

<p>Die <a href="Slater-Bedingung" title="Slater-Bedingung">Slater-Bedingung</a> ist eine Voraussetzung an das primale Problem, die garantiert, dass <a href="Starke_Dualit%C3%A4t" class="mw-redirect" title="Starke Dualität">starke Dualität</a> gilt. Sie fordert, dass das Problem einen Punkt besitzt, der die Gleichungsnebenbedingungen erfüllt, und alle Ungleichungsnebenbedingungen strikt erfüllt, dass also <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)\prec _{K}0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)\prec _{K}0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/615c92c3233d3192dabe5d54e95637d5febae337.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.372ex; height:2.843ex;" alt="{\displaystyle f(x)\prec _{K}0}" loading="lazy"></span> bzw. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)\succ _{K}0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)\succ _{K}0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4063f379ce8f3285c1a0b228815d6517cfddd745.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.372ex; height:2.843ex;" alt="{\displaystyle f(x)\succ _{K}0}" loading="lazy"></span> für mindestens einen Punkt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> in allen Ungleichungsnebenbedingungen des Problems gleichzeitig gilt. Da aber <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\succ _{S_{+}^{n}}0}">

<msub>

</mrow>

</mrow>

</msubsup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\succ _{S_{+}^{n}}0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c7fbb0b1170d07c3e54f82b30e260d45e44bd5aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:8.683ex; height:3.009ex;" alt="{\displaystyle X\succ _{S_{+}^{n}}0}" loading="lazy"></span> genau dann gilt, wenn <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\in \operatorname {Int} (S_{+}^{n})}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X\in \operatorname {Int} (S_{+}^{n})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/04863efc9ddfb109ce09a542413b2e4e83a2cb8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.602ex; height:3.009ex;" alt="{\displaystyle X\in \operatorname {Int} (S_{+}^{n})}" loading="lazy"></span> ist, was wiederum äquivalent dazu ist, dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> eine positiv definite Matrix ist, ist die Slater-Bedingung für SDPs bereits erfüllt, wenn es eine positiv definite Matrix gibt, welche die Gleichungsnebenbedingungen erfüllt.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Florian Jarre, Josef Stoer: <i>Optimierung.</i> Springer, Berlin 2004, ISBN 3-540-43575-1.</li>

<li>Johannes Jahn: <i>Introduction to the Theory of Nonlinear Optimization.</i> 3. Auflage. Springer, Berlin 2007, ISBN 978-3-540-49378-5.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Florian Jarre, Josef Stoer: <i>Optimierung.</i> Springer, Berlin 2004, S. 419.</span>

</li>

</ol>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><span class="cite">Christoph Helmberg: <a rel="nofollow" class="external text" href="https://www-user.tu-chemnitz.de/~helmberg/semidef.html"><i>Seite mit vielen weiterführenden Links.</i></a><span class="Abrufdatum"> Abgerufen am 19. Juli 2008</span> (englisch).</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3ASemidefinite+Programmierung&rft.title=Seite+mit+vielen+weiterf%C3%BChrenden+Links&rft.description=Seite+mit+vielen+weiterf%C3%BChrenden+Links&rft.identifier=&rft.creator=Christoph%26%2332%3BHelmberg&rft.date=&rft.language=englisch"> </span></li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-12-21" href="https://de.wikipedia.org/wiki/?title=Semidefinite_Programmierung&oldid=251439764">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>